package leetcode_400;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *@author 周杨
 *LargestDivisibleSubset_368_ 给定一个数组 返回其最大子数组 这个子数组要满足:其中所有元素 都是互为倍数的
 *describe:先排序 然后用动态规划解决 用两个动归数组 保存当前最大长度和当前最大长度指向的坐标  AC 98%
 *2018年7月9日 上午11:44:57
 */
public class LargestDivisibleSubset_368_ {

	public static void main(String[] args) {
		LargestDivisibleSubset_368_ test=new LargestDivisibleSubset_368_();
		test.largestDivisibleSubset(new int[] {3,4,8,16});

	}
	public List<Integer> largestDivisibleSubset(int[] nums) {
		List<Integer> res=new ArrayList<Integer>();
		if(nums.length==0)
			return res;
		Arrays.sort(nums);
		int []dp=new int[nums.length];
		int []memory=new int[nums.length];
		dp[0]=1;
		memory[0]=-1;
		int max=1;
		int maxIndex=0;
		for(int i=1;i<nums.length;++i) {
			int curMax=1;
			int curIndex=-1;
			for(int j=0;j<i;++j) {
				if(nums[i]%nums[j]==0) {
					if(dp[j]+1>curMax) {
						curMax=dp[j]+1;
						curIndex=j;
					}
				}
			}
			dp[i]=curMax;
			memory[i]=curIndex;
			if(curMax>max) {
				max=curMax;
				maxIndex=i;
			}
		}
		int index=maxIndex;
		while(index!=-1) {
			res.add(nums[index]);
			index=memory[index];
		}
		return res;
    }
}
